package unl.cse.graphs;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;



public class JohnsonTrotter implements Cloneable{
	
	private List<Element> permutation;
	
	
	public List<Element> getPermutation() {
		return permutation;
	}


	public void setPermutation(List<Element> permutation) {
		this.permutation = permutation;
	}



	private List<List<Element>> permutations;
	
	
	
	public JohnsonTrotter(){
		permutation = new ArrayList<Element>();
		permutations = new ArrayList<List<Element>>();
	}
	
	
	public void initialize(int num){
		if(num < 0){
			return;
		}
		
		
		
		for(int i = 0; i < num; i++){
			permutation.add(new Element(i, true, Direction.LEFT));
		}
		
		
	}
	
	
	

	public boolean generatePermutation(){
		
		
		
//		initialize(num);
		
		 if(hasMobileElement(permutation)){
			
//			List<Element> elements = new ArrayList<Element>(permutation);
//			permutations.add(elements);
			
			//find the largest mobile element
			int k_index = findLargestMobileIndex(permutation);
			Element k = permutation.get(k_index);
			
			int leftIndex = 0;
			int rightIndex = 0;
			
			if(k.getDirection() == Direction.LEFT){
				if(k_index - 1 >= 0){
					 leftIndex = k_index - 1;
					 Collections.swap(permutation, k_index, leftIndex);
					 
					 
				}
				
				
			}
			else{
				
				if(k_index + 1 < permutation.size()){
					 rightIndex = k_index + 1;
					 Collections.swap(permutation, k_index, rightIndex);
					
				}
				
				
				
			}
			
			//reverse the direction of all elements larger than K
			for(Element element: permutation){
				if(element.getValue() > k.getValue()){
					element.inverseDirection();
				}
			}
			
			//reset Mobile value
			resetMobile(permutation);
			
			return true;
			
			
		}
		 
		 else{
			 return false;
		 }
		
		
		
		
	}
	
	
	public void resetMobile(List<Element> permutation) {
		for(int i = 0; i < permutation.size(); i++){
			//most left element and its direction is left
			if(i == 0 && permutation.get(0).getDirection()==Direction.LEFT){
				permutation.get(0).setMobile(false);
				//most right element and its direction is right
			}else if(i == permutation.size()-1 && permutation.get(i).getDirection()==Direction.RIGHT){
				permutation.get(i).setMobile(false);
				
				//the element is smaller than the element it points
			}else if(permutation.get(i).getDirection() == Direction.LEFT && permutation.get(i).getValue() < permutation.get(i-1).getValue() ){
				permutation.get(i).setMobile(false);
			}else if(permutation.get(i).getDirection() == Direction.RIGHT && permutation.get(i).getValue() < permutation.get(i+1).getValue()){
				permutation.get(i).setMobile(false);
			}else{
				permutation.get(i).setMobile(true);
			}
		}
		
	}


	public int findLargestMobileIndex(List<Element> permutation) {
		
		int max = Integer.MIN_VALUE;
		int max_index = 0;
		for(int i = 0; i < permutation.size(); i++){
			if(permutation.get(i).isMobile() && permutation.get(i).getValue() > max){
				max = permutation.get(i).getValue();
				max_index = i;
			}
		}
		return max_index;
	}


	public boolean hasMobileElement(List<Element> elements) {
		for(Element element: elements){
			if(element.isMobile()){
				return true;
			}
		}
		return false;
	}
	

	public List<List<Integer>> getPermutations(){
		
		List<List<Integer>> perms = new ArrayList<List<Integer>>();
		for(List<Element> permutation: permutations){
			List<Integer> perm = new ArrayList<Integer>();
			for(Element element: permutation){
				perm.add(element.getValue());
			}
			perms.add(perm);
			
		}
		
		return perms;
	}
	
	
	public String toString(){
		
			for(Element element: permutation){
				System.out.print(element.getValue() + " ");
			}
			System.out.println();
		
		
		return "";
	}
	


	public static void main(String[] args) {
		
		long start = System.currentTimeMillis();
		
		JohnsonTrotter test = new JohnsonTrotter();
		
		
		test.initialize(2);
		
		test.toString();
		
		while(test.generatePermutation()){
		
		test.toString();
		}
		System.out.println(test.getPermutations().size());
		
		 // Get the Java runtime
	    Runtime runtime = Runtime.getRuntime();
	    // Run the garbage collector
	    runtime.gc();
	    // Calculate the used memory
	    long memory = runtime.totalMemory() - runtime.freeMemory();
	    System.out.println("Used memory is bytes: " + memory);
	    
	  
		
		long end = System.currentTimeMillis();
		
		long runningTime = end - start;
		System.out.println(runningTime);
		
		

	}

}
